package 动态规划;

public class leetcode343 {

	/**
	 * 这个题 就很抽象！
	 *这种 暴力递归的 想法， 或者 这种思想就很抽象 
	 */
	
	
	public int solution(int n) {
		if(n == 1)
			return 0;
		if(n == 2)
			return 1;
		if(n == 3)
			return 2;
		int ans = 0;
		/**
		 * 仔细 去想 一下 这整个 暴力枚举的过程！
		 * 其实这个暴力 递归 枚举 了所有的过程！
		 */
		for(int index = 2;index < n;index++) {
			int temp = Math.max(index * (n - index), index * solution(n - index));
			ans = Math.max(ans, temp);
		}
		return ans;
	}
	
	public int dp(int N) {
		int dp [] = new int [N + 1];
		dp[1] = 0;
		dp[2] = 1;
//		dp[3] = 2;
		for(int n = 3;n <= N;n++ ) {
			for(int index = 2;index < n;index++) {
				dp[n] = Math.max(dp[n], Math.max(index * (n - index), index * dp[n - index]));
			}
		}
		return dp[N];
	}
	
}
